package com.explorati.interview.interview.chapterfifteen.sort;

/**
 * 插入排序改进：将原先的交换swap操作改为如果后一个元素比前一个元素大，则将后一个元素赋值为前一个元素，最后循环退出时的位置就是该元素插入的位置
 * 所以之前需拷贝一份要插入的元素
 * 
 * @author explorati
 *
 * @param <E>
 */
public class InsertSortV2<E> implements Sort {

	@Override
	public void sort(Comparable[] arr) {
		for (int i = 1; i < arr.length; i++) {
			// 寻找元素arr[i]合适的插入位置
			E temp = (E) arr[i];
			// j保存元素temp应该插入的位置
			int j;
			for (j = i; j > 0 && arr[j - 1].compareTo(temp) > 0; j--) {
				arr[j] = arr[j - 1];
			}
			if (j != i) {
				arr[j] = (Comparable) temp;
			}

		}
	}

}
